package tree;

public class leetCode208_Trie {



}

class Trie {

    private Trie[] children = null;
    private boolean isEnd = false;

    public Trie() {
        this.isEnd = false;
        this.children = new Trie[26];
    }

    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int a = c - 'a';
            if(node.children[a] == null){
                node.children[a] = new Trie();
            }
            node = node.children[a];
        }
        node.isEnd = true;

    }

    public boolean search(String word) {
        Trie trie = searchPrefix(word);
        return  trie != null && trie.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (char c : prefix.toCharArray()) {
            int a = c - 'a';
            if(node.children[a] == null){
                return null;
            }
            node = node.children[a];
        }
        return node;
    }
}
